#include "RR.h"
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  void *data;        // 指向数据的指针
  struct Node *next; // 指向下一个节点的指针
} Node;
typedef struct Queue
{
  Node *front; // 指向队列头的指针
  Node *rear;  // 指向队列尾的指针
} Queue;
// 初始化队列
Queue *
createQueue ()
{
  Queue *q = (Queue *)malloc (sizeof (Queue));
  q->front = q->rear = NULL;
  return q;
}

// 入队操作
void
enqueue (Queue *q, void *data)
{
  Node *temp = (Node *)malloc (sizeof (Node));
  temp->data = data;
  temp->next = NULL;
  if (q->rear == NULL)
    {
      q->front = q->rear = temp;
      return;
    }
  q->rear->next = temp;
  q->rear = temp;
}

// 出队操作
void *
dequeue (Queue *q)
{
  if (q->front == NULL)
    {
      return NULL;
    }
  Node *temp = q->front;
  void *data = temp->data;
  q->front = q->front->next;

  if (q->front == NULL)
    {
      q->rear = NULL;
    }
  free (temp);
  return data;
}

// 检查队列是否为空
int
isEmpty (Queue *q)
{
  return q->front == NULL;
}

/**
 * 函数: calculateTimes
 * 功能: 根据时间片轮转调度算法计算每个进程的完成时间、周转时间和等待时间
 *
 * 参数:
 *  - processes: 指向包含多个进程信息的数组
 *  - n: 进程数量
 *  - time_slice: 时间片长度
 *
 * 描述:
 *  计算进程的完成时间，周转时间和等待时间并存在结构体中即可
 */
// 计算进程调度时间
void
calculateTimes (Process *processes, int n, int time_slice)
{
  Queue *qe = createQueue ();
  int remain_num = n;
  int time = 0;
  int *qflag = (int *)malloc (sizeof (int) * n);
  for (int i = 0; i < n; i++)
    {
      qflag[i] = 0;
    }

  // 将新到达的进程加入队列
  for (int j = 0; j < n; j++)
    {
      if (processes[j].arrival_time <= time && qflag[j] == 0)
        {
          qflag[j] = 1;
          enqueue (qe, &processes[j]);
        }
    }
  while (remain_num > 0)
    {

      // 从队列中取出一个进程执行
      if (!isEmpty (qe))
        {
          Process *pt = (Process *)dequeue (qe);

          if (pt->remaining_time <= time_slice)
            {
              time += pt->remaining_time;
              pt->completion_time = time;
              pt->turnaround_time = pt->completion_time - pt->arrival_time;
              pt->waiting_time = pt->turnaround_time - pt->burst_time;
              pt->remaining_time = 0;
              remain_num--;
            }
          else
            {
              time += time_slice;
              pt->remaining_time -= time_slice;
              // 将新到达的进程加入队列
              for (int j = 0; j < n; j++)
                {
                  if (processes[j].arrival_time <= time && qflag[j] == 0)
                    {
                      qflag[j] = 1;
                      enqueue (qe, &processes[j]);
                    }
                }
              enqueue (qe, pt); // 没执行完在塞回去
            }
        }
      else
        {

          time++; // 没有进程可执行时，时间向前推进
        }
    }

  free (qe);
}
